The three stage Clos network is generally considered the most basic multistage interconnection network (MIN), and is often extendible to MINs with more than three stages. In a symmetric three-stage network, the first/input stage and the last/output stage have r, n.times.m switches such as crossbar switches. The center stage has m, r.times.r switches. n inlets and r outlets on each input and output switch respectively, are the inputs and outputs of the network. The input and output stage switches are each linked to every center stage switch. A separate link exists between every center switch and every input switch and between every center switch and every output switch. The inlets and outlets are referred to as external links and the links connecting to the center stage are internal links.
In classical circuit switching, three types of nonblocking properties have been extensively studied. V. E. Benes, "Mathematical Theory of Connecting Networks and Telephone traffic" (Academic Press, 1965), hereby incorporated by reference as if fully set forth herein. A request, which can be any communication type, e.g., a telephone call and data communications, between an inlet and an outlet is routable if there exists a path of links connecting them such that no link on the path is used by any other connection paths. A network is strictly nonblocking if regardless of the routing of existing connections in the network, a new request is always routable. A network is wide-sense nonblocking ("WSNB") if a new request is always routable as long as all previous requests were routed according to a given routing algorithm. A network is rearrangeably nonblocking, or simply rearrangeable, if a new request is always routable given that existing connections can be rerouted. Strictly nonblocking implies WSNB which implies rearrange able.
Every request has an associated weight, or load w which can be thought of as the bandwidth requirement of that request. As each link has a load capacity .beta., only a finite number of requests, denoted by the variable set (u,v,w) where u is an inlet, v an outlet and w a load, can be linked to a particular interconnection unit. The loads of all requests to be routed by a network can be normalized such that w has a value between zero and one with each internal link having a capacity of one. Accordingly, each internal link can carry multiple requests as long as the sum of loads of these requests does not exceed a value of one. Furthermore a request can only be routed from inlet u to outlet v if the sum of loads of all requests from inlet u to any outlet other than v does not exceed .beta.-w, and the sum of loads of all requests from all inlets other than u to outlet v does not exceed .beta.-w. This is equivalent to setting the load capacity of an external link to be .beta..
For the remainder of this application, .left brkt-bot.x.right brkt-bot. denotes the largest integer not exceeding x, and .left brkt-top.x.right brkt-top. denotes the smallest integer not less than x. With respect to strictly nonblocking multirate three-stage Clos networks, where B denotes the maximum load of a request, and b the minimum load, it has been shown that a network denoted by C (n,m,r), carrying requests having a load between b and 1, is strictly nonblocking where the number of center stage interconnection units is at least 2 .left brkt-bot.n-1/b.right brkt-bot.+3. Melen and Turner, "Nonblocking multirate networks," SIAM J. Comput., 18 (1989), pp. 301-313, hereby incorporated by reference as if fully set forth herein. For .beta.=1, this result was later reduced to 2(n-1).left brkt-bot.1/b.right brkt-bot.+1. Chung and Ross, "On nonblocking multirate interconnection networks," SIAM J. Comput. 20 (1991) pp. 726-36, hereby incorporated by reference as if fully set forth herein.
It has also been shown that a network carrying requests having a load between zero and B, is multi-rate strictly nonblocking if the number of center interconnection units is at least ##EQU1## This will be denoted as m.sup.0 for future reference.
Niestegge, "Nonblocking multirate switching networks," Traffic Eng. for ISDN Desig. and Plan., M. Bonatti and M. Decina (Eds.), Elsevier, 1988, hereby incorporated by reference as if fully set forth herein, demonstrated that in general, a network carrying two loads b and B is also strictly nonblocking for more than two rates if b is an integer multiple of all of the rates and 1, and m is at least EQU 2.left brkt-bot.(n-B)/(1-B+b).right brkt-bot.+1.
It has also been shown that a single rate network where the reciprocal of the load is an integer, is strictly nonblocking with 2n-1 center interconnection units.
Note that as B approaches one and b approaches zero, the number of center interconnection units required is unbounded in all of the above formulas. Thus as the range of loads increases, the number of center interconnection units increases, resulting in higher cost and more complex switching networks. In response to this problem, it has been recognized that nonblocking can be achieved even without a strictly nonblocking architecture. Rather, by using an appropriate request routing algorithm, WSNB may help to limit the number of center interconnection units.
For example, consider a network carrying requests whose loads are either 1.0 or 0.25, and where each input switch has four inlets, i.e., n=4. From the foregoing formulas, strictly nonblocking network would require at least twenty five interconnection units. However, if all of the requests with a load of 1.0 are routed through one group of center interconnection units and all requests with a 0.25 load are routed through another group, the network problem could be analyzed as two single-rate networks, each being nonblocking with only seven center interconnection units, as shown by the formula 2n-1. Hence m is reduced from twenty five to fourteen.
The prior art has achieved a WSNB network with 8n center interconnection units where n is the number of inlets per input stage switch, and a link load capacity of .beta.=1. Notwithstanding the above example and despite the efficiency that can be realized with WSNB, assuming the proper routing algorithm, there has been very little further development of multirate WSNB in the prior art, to reduce this number further.